期刊
  出版年
  关键词
结果中检索 Open Search
Please wait a minute...
选择: 显示/隐藏图片
1. 基于有向无环图的倒排链等字长划分压缩算法
姜琨, 刘征, 朱磊, 李晓星
计算机应用    2021, 41 (3): 727-732.   DOI: 10.11772/j.issn.1001-9081.2020060874
摘要467)      PDF (905KB)(427)    收藏
在搜索引擎的倒排索引等字长(FWA)类型压缩算法中,倒排链的“贪心”分块划分策略和码字信息的交错存储使算法难以达到最优的压缩效果。针对上述问题,提出了一种基于有向无环图(DAG)的FWA划分压缩算法。首先,考虑到互联网网页聚类特性带来的倒排链小数字信息,设计了一种数据区为64位分块的新型FWA压缩格式。该压缩格式通过4位的指示区将数据区划分为16种适合于连续小数字压缩的存储模式,并将倒排链每个分块的指示位和数据位分类存储,从而保证了较好的批量解压性能。其次,在新压缩格式的基础上提出一种基于DAG描述的倒排链FWA划分压缩方法——固定字对齐划分(WAP)算法。该算法利用DAG将倒排链分块划分问题归结为单源最短路径(SSSP)问题,并考虑FWA压缩格式中数据区存储模式的限制条件来确定SSSP问题的结构形式和递归定义。然后,给出了采用动态规划求解SSSP问题并形成最优划分向量的伪码和算法复杂度,并对S9、S16、S8b等传统FWA算法的原有存储模式进行了基于DAG的划分优化,把优化前后的算法的计算复杂度进行比较分析。最后,使用仿真整数序列数据和文本检索会议(TREC) GOV2网页索引数据进行压缩性能实验。实验结果表明,相较于传统FWA类型算法,基于DAG的FWA划分算法在通过批量解压和划分优化技术提升算法的压缩率和解压速度同时,对连续小数字整数序列进行压缩时能够获得比传统参照框架(FOR)类型算法更高的压缩率。
参考文献 | 相关文章 | 多维度评价